package 中等.搜索.回溯;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，
 * 找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 注意：解集不能包含重复的组合。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/combination-sum-ii
 */
public class 组合总和II_40 {

    public static void main(String[] args) {

    }

    /**
     * 回溯
     * 1，将原数组排序，每个位置，只相同数字最后一个未被搜索过的数字
     * 2，[1,2,1] 和 [1,1,2] 是一样的，下次搜索只能搜索 >= 上次搜索的数子
     * 并且下次搜索的起点是相同数字的第一个数字
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);

        List<List<Integer>> lists = new ArrayList<>();

        dfs(new ArrayList<>(), target, 0, new boolean[candidates.length], candidates, lists);

        return lists;
    }

    private void dfs(List<Integer> curList, int target, int begin, boolean[] visited, int[] candidates, List<List<Integer>> lists) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(curList));
            return;
        }

        int idx = begin;
        while (idx < candidates.length) {
            int nextBegin = idx;
            while (idx < visited.length && visited[idx] ||
                    idx + 1 < candidates.length && !visited[idx + 1] && candidates[idx] == candidates[idx + 1]) {
                idx++;
            }

            if (idx < visited.length) {
                visited[idx] = true;
                curList.add(candidates[idx]);

                dfs(curList, target - candidates[idx], nextBegin, visited, candidates, lists);

                visited[idx] = false;
                curList.remove(curList.size() - 1);
            }

            idx++;
        }
    }

}
